/*
定义 dp[i]   表示以i结尾的最大连续子数组和
dp[i] = dp[i-1] + v[i]      dp[i-1] >=0
      = v[i]        dp[i-1]<0

最后在dp数组中取最大值
*/

class Solution 
{
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp;
        int max = INT_MIN;
        for(int i =0;i<nums.size();i++)
        {
            if(i==0)
            {
                dp.push_back(nums[i]);
                max = max > dp[i] ?max : dp[i];
            }
                
            else
            {
                if(dp[i-1]>=0)
                   dp.push_back(dp[i-1]+nums[i]); 
                else
                   dp.push_back(nums[i]);  
                
                max = max > dp[i] ?max : dp[i];
            }

        }
        return max;
    }
};